// 2025/5/7
// 最长上升子序列(二)

class Solution {
    public:
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * 该数组最长严格上升子序列的长度
         * @param a int整型vector 给定的数组
         * @return int整型
         */
        int LIS(vector<int>& a) {
            // write code here
            vector<int> lends;
            int n = a.size();
            for(int i = 0; i < n; i++)
            {
                if(lends.empty() || lends.back() < a[i])
                {
                    lends.emplace_back(a[i]);
                }
                else 
                {
                    int left = 0, right = lends.size() - 1;
                    int mid, aim;
                    while(left <= right)
                    {
                        mid = (left + right) >> 1;
                        if(lends[mid] >= a[i])
                        {
                            aim = mid;
                            right = mid - 1;
                        }
                        else
                            left = mid + 1;
                    }
                    lends[aim] = a[i];
                }
            }
            return lends.size();
        }
    };